package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/7/12 9:47
 */
public class IntervalNumbers {

    private static final int[] arr = {1, 2, 4, 1, 7, 8, 3};

    public int recOpt(int[] arr, int i) {
        if (i == 0) return arr[0];
        else if (i == 1) return Math.max(arr[0], arr[1]);
        else {
            int a = recOpt(arr, i - 2) + arr[i];
            int b = recOpt(arr, i - 1);
            return Math.max(a, b);
        }
    }

    // 动态规划推荐使用迭代写法，避免overlap问题
    public int dpOpt(int[] arr) {
        int n = arr.length;
        int[] opt = new int[n];
        opt[0] = arr[0];
        opt[1] = arr[1];
        int max = Math.max(arr[0], arr[1]);
        for (int j = 2; j < n; j++) {
            opt[j] = Math.max(opt[j - 1], opt[j - 2] + arr[j]);
            if (opt[j] > max) max = opt[j];
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new IntervalNumbers().dpOpt(arr));
    }

}
